package cn.dglydrpy.study.algorithm.od;

/**
 * @author Yyy
 * @date 2024/11/7 16:53
 * @description TODO
 * 有一辆汽车要从地图左上角开往右下角，地图中数字表示不同地区的耗油量或加油站（-1 表示加油站可加满油，容量最大 100；0 表示障碍物），
 * 求汽车确保从起点到达终点所需的最少初始油量，若无法到达终点则返回 -1。
 */
public class Od0019_DriverCar {
    public static void main(String[] args) {
        
        int M = 2;
        int N = 2;
        int[][] board = new int[][]{
            new int[]{10,20},
            new int[]{30,40}
        };
        
        int ans = myAnswer(board,M,N);
        
    }

    private static int myAnswer(int[][] board,int M,int N) {
        int ans = -1;
        
        ans = process(board,0,0);
        
        return ans;
    }

    // 从(i,j)位置到右下角需要的最小初始耗油量
    private static int process(int[][] board,int i, int j) {
        
        int M = board.length;
        int N = board[0].length;
        
        if(i < 0 || j<0 || i>M-1 || j > N-1){
            return Integer.MAX_VALUE;
        }
        
        if(board[i][j] > 100){
            return Integer.MAX_VALUE;
        }
        
        if(board[i][j] == -1){
            
        }
        
        int p1 = process(board,i-1,j);
        int p2 = process(board,i+1,j);
        int p3 = process(board,i,j+1);
        int p4 = process(board,i,j-1);

        int min = Math.min(Math.min(p1,p2),Math.min(p3,p4));
        return min;
    }

}
